package leetcode;

//There are N gas stations along a circular route, where the amount of gas at station i isgas[i].
//You have a car with an unlimited gas tank and it costscost[i]of gas to travel from station i to its next station 
//(i+1). You begin the journey with an empty tank at one of the gas stations.
//Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
//Note:  The solution is guaranteed to be unique.
public class GasStation {
	public static void main(String[] args) {
		GasStation gasStation = new GasStation();
		int[] gas = {2,4}, cost = {3,4};
		System.out.println(gasStation.canCompleteCircuit(gas, cost));
	}

	public int canCompleteCircuit(int[] gas, int[] cost) {
		// this problem can cast to max sum of the longest sub array
		int[] remain = new int[gas.length];
		for (int i = 0; i < gas.length; i++) {
			remain[i] = gas[i] - cost[i];
		}
		//获取到最大和
		int maxSum = remain[0], curSum = 0, index = 0;
		for (int i = 0; i < remain.length; i++) {
			if (curSum < 0) {
				curSum = remain[i];
				index = i;
			} else {
				curSum += remain[i];
			}
			maxSum = Math.max(curSum, maxSum);
		}
		System.out.println(maxSum);
		//Attention, if there is a way can go through all the circular , 
		//the array of remain's sum must big than 0
		int sum = 0;
		for (int count = 0; count < remain.length; ++count) {
			sum += remain[count];
		}
		if (sum < 0)
			return -1;
		//如果最大和都不能走完(< 0)，那么肯定不能走完
		//如果最大和大于0并且sum大于0，说明可以走完
		return maxSum >= 0 ? index : -1;
	}
}
